<head>
    <meta charset="UTF-8">
<title>算法训练 Let Me Tell You a Story</title>
<link rel="stylesheet" href="../css/main.css">
</head>
 <p>问题描述<br />
这个故事发生在...<br />
很久以前，国王Tryone the Fair有4个大臣。第1个大臣（国王的顶级建议者）每周要被支付7块金子。第2个大臣每周要被支付4块金子。第3、4个大臣每周都要被支付6块金子。不幸的是，一天，Tryone偶然地忘了照片复制器中的大臣补偿表，并且这个表格在Kingdom Times的头版的末尾。就此，第2个大臣要求向国王讲话，因为他自己的薪水比比自己等级低的第3个大臣的薪水低而心烦意乱。<br />
他的不公平的国王Tryone看到没有更好的方法比解雇第3个大臣更好的方法了。毕竟，降低第3个大臣的薪水，提升第2个大臣的薪水，或者改变工作的头衔，在国王看来，都是不公平的解决方法。并且我们有什么资格质问国王Tyrone呢？当然，解雇第3个大臣不能解决这个问题。第2个大臣继续抱怨，因为他的薪水仍然比第4个大臣的薪水低。因此国王Tryone也解雇了第4个大臣。这时，这两个剩下的大臣都没有抱怨了，所有人在这以后都快乐地生活。<br />
...等一下。我把这个搅乱了。对不起。我的记忆不是它之前的那样。等一下...对。国王Tyrone是公平的。4个大臣。被支付的钱数分别是7、4、6和6。啊，对。结局是这样的...<br />
当第2个大臣抱怨不公平的时候，国王Tyrone解雇了第1个大臣。有些人也许说这有一点这有点残酷，因为第1个大臣无论如何都与这个事情没有关系，但是我们不应该质问国王Tyrone。显然，第二个大臣仍然抱怨，因此国王Tyrone简单地解雇了他。剩下的两个大臣，每个人都被支付了至少比任何比自己等级低的大臣高的薪水，因此没有人抱怨。并且这以后所有人快乐地生活。<br />
这样更好...我觉得。也许？现在我不再确定了。我确定有N个大臣，并且我清晰地记得他们的薪水。我也知道每当一个大臣的薪水比比他等级低的大臣的薪水低的时候，某个人就会抱怨，并且某个大臣就会被解雇；但是任何大臣，不管他是否与这个问题有任何关系，都有可能被解雇。一直有大臣会被解雇，直到没有人抱怨，因为薪水的总和是不会增加的。这时，解雇停止了。但是我记不得大臣被解雇的顺序。<br />
你能帮助我修复我的故事吗？或者至少告诉我我能够讲出多少个不同的故事？两个故事不同当且仅当两个故事中被解雇的大臣的顺序不同。<br />
输入格式<br />
输入中的第一行包含测试数据的组数。之后是T组数据。每组数据包含两行。第一行包含一个整数N，第二行包含N个整数，按照第1个到第N个大臣的顺序描述所有大臣的薪水。<br />
输出格式<br />
对于每组测试数据，输出一行，格式为&quot;Case #x: y&quot;，这里x是测试数据的编号（从1开始），y表示可能讲出的故事的数量，对10007取模。<br />
样例输入<br />
3<br />
4<br />
7 4 6 6<br />
4<br />
90 80 70 60<br />
2<br />
7 8<br />
样例输出<br />
Case #1: 14<br />
Case #2: 1<br />
Case #3: 2<br />
数据规模和约定<br />
对于30%的数据，1&lt;=T&lt;=20，1&lt;=N&lt;=100；<br />
对于另外70%的数据，1&lt;=T&lt;=5，1&lt;=N&lt;=2000。<br />
对于全部的数据，所有大臣的薪水均为正整数且不超过10000。</p>